package num1625;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/4/15 5:37
 * @Desc :
 */
class LRUCache {
  private DoubleLinkedList<Integer, Integer> cache;

  public LRUCache(int capacity) {
    cache = new DoubleLinkedList<>(capacity);
  }

  public int get(int key) {
    Node<Integer, Integer> res = cache.get(key);
    if (res != null)
      return res.getValue();
    else
      return -1;
  }

  public void put(int key, int value) {
    cache.put(key, value);
  }

  private static class DoubleLinkedList<K, V> {
    private int capacity;
    private int count;
    private Node<K, V> head;
    private Node<K, V> tail;

    public DoubleLinkedList(int capacity) {
      this.capacity = capacity;
      count = 0;
      head = new Node<>();
      tail = new Node<>();
      head.next = tail;
      tail.prev = head;
    }

    public void put(K key, V value) {
      // 看看本地有没有这个key，有的话，就移到最前面，并且重新设置值
      Node<K, V> node = get(key);
      if (node != null) {
        moveToHead(node);
        node.setValue(value);
        return;
      }
      // 本地没有，就新建一个，并且插入到最前面
      node = new Node<>(key, value);
      insertHead(node);
      // 如果超内存了,删除尾部结点
      if (++count > capacity) {
        deleteTail();
        count--;
      }
    }

    public Node<K, V> get(K key) {
      Node<K, V> node = head.getNext();
      while (node != null && node != tail) {
        if (node.getKey().equals(key)) {
          // 如果不是在第一个元素，那就将它移到最前面，如果是，那就不用移动了
          if (node.getPrev() != head)
            moveToHead(node);
          return node;
        }
        node = node.getNext();
      }
      return null;
    }

    public void moveToHead(Node<K, V> node) {
      // 给前后两个结点配对
      node.getNext().setPrev(node.getPrev());
      node.getPrev().setNext(node.getNext());
      // 前一个结点指向head，后一个结点指向head的下一个结点
      node.setNext(head.getNext());
      node.setPrev(head);
      //  让head和head的后一个结点，都指向自己
      head.getNext().setPrev(node);
      head.setNext(node);
    }

    public void insertHead(Node<K, V> node) {
      // 将node前后指向head和head的下一个
      node.setNext(head.getNext());
      node.setPrev(head);
      // 修改head和head下一个结点的指向，指向自己
      head.getNext().setPrev(node);
      head.setNext(node);
    }

    public void deleteTail() {
      tail.setPrev(tail.getPrev().getPrev());
      tail.getPrev().setNext(tail);  // 新的前一个结点，让他修改为指向自己
    }
  }

  private static class Node<K, V> {
    private K key;
    private V value;
    private Node<K, V> next = null;
    private Node<K, V> prev = null;

    public Node() {
    }

    public Node(K key, V value) {
      this.key = key;
      this.value = value;
    }

    public Node(K key, V value, Node<K, V> next, Node<K, V> prev) {
      this.key = key;
      this.value = value;
      this.next = next;
      this.prev = prev;
    }

    public K getKey() {
      return key;
    }

    public void setKey(K key) {
      this.key = key;
    }

    public V getValue() {
      return value;
    }

    public void setValue(V value) {
      this.value = value;
    }

    public Node<K, V> getNext() {
      return next;
    }

    public void setNext(Node<K, V> next) {
      this.next = next;
    }

    public Node<K, V> getPrev() {
      return prev;
    }

    public void setPrev(Node<K, V> prev) {
      this.prev = prev;
    }
  }
}
